/*
 * @Author: your name
 * @Date: 2021-10-05 13:00:32
 * @LastEditTime: 2021-10-05 13:00:32
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\1.6二分查找\模板\allbinary.cpp
 */
#include<iostream>
using namespace std;

#define L 10

void binary1(int a[],int low,int high,int find);
void binary2(int a[],int low,int high,int find);
void binary3(int a[],int low,int high,int find);
void binary3_(int a[],int low,int high,int find);
void binary4(int a[],int low,int high,int find);
void binary4_(int a[],int low,int high,int find);

int main(){
	int a[L] = {0,1,1,2,2,2,2,2,9,9};
	cout << "初始数组如下" << endl;
	for(int i=0; i<L; i++){
		cout << a[i] << " ";
	}
	cout << endl;
	for(int i=0; i<L; i++){
		cout << i << " ";
	}
	cout << endl;
	
	//调用binary函数
	while(1){
		int n;
		cin >> n;
		if(n == -1){
			return 0;
		}
//		binary1(a,0,L-1,n); 
//		binary2(a,0,L-1,n);
		binary3(a,0,L-1,n);
		binary3_(a,0,L-1,n);
		binary4(a,0,L-1,n);
		binary4_(a,0,L-1,n);
	}
		return 0;
} 

void binary1(int a[],int low,int high,int find)
{
	/*
		1.find存在,输出最左边的index
		2.find不存在,输出第一个大于find数字的index 
			2.1 比如最后剩下 5 7,而find=6
			2.2 6 > 5 右半区间 
			2.3 所以输出7的下标 
	*/
	int left = low;
	int right = high;
	int mid;
	while(left < right){
		mid = (left+right)/2; //左开 
		if(find <= a[mid]){
			right = mid;
		}else{
			left = mid+1;
		}
	}
	cout << "find index:" << left << endl;
}

void binary2(int a[],int low,int high,int find)
{
	/*
		1.find存在,输出最右边的index
		2.find不存在,输出第一个小于find数字的index 
			2.1 比如最后剩下 5 7,而find=6
			2.2 6 > 5 右半区间 
			2.3 所以输出5的下标 
	*/
	int left = low;
	int right = high;
	int mid;
	while(left < right){
		mid = (left+right+1)/2; //右开 
		if(find < a[mid]){
			right = mid-1;
		}else{
			left = mid;
		}
	}
	cout << "find index:" << left << endl;
}

void binary3(int a[],int low,int high,int find)
{
	/*

	*/
	int left = low;
	int right = high;
	int mid;
	while(left <= right){
		mid = (left+right)/2; //右开 
		if(find < a[mid]){
			right = mid-1;
		}else{
			left = mid+1;
		}
	}
	cout << "find left:" << left << " right:" << right << endl;
}

void binary3_(int a[],int low,int high,int find)
{
	/*

	*/
	int left = low;
	int right = high;
	int mid;
	while(left <= right){
		mid = (left+right+1)/2; //右开 
		if(find < a[mid]){
			right = mid-1;
		}else{
			left = mid+1;
		}
	}
	cout << "find left:" << left << " right:" << right << endl;
}

void binary4(int a[],int low,int high,int find)
{
	/*

	*/
	int left = low;
	int right = high;
	int mid;
	while(left <= right){
		mid = (left+right)/2; //右开 
		if(find <= a[mid]){
			right = mid-1;
		}else{
			left = mid+1;
		}
	}
	cout << "find left:" << left << " right:" << right << endl;
}

void binary4_(int a[],int low,int high,int find)
{
	/*

	*/
	int left = low;
	int right = high;
	int mid;
	while(left <= right){
		mid = (left+right+1)/2; //右开 
		if(find <= a[mid]){
			right = mid-1;
		}else{
			left = mid+1;
		}
	}
	cout << "find left:" << left << " right:" << right << endl;
}